
//911.在线选举
class TopVotedCandidate {
    //进行优化使用两个数组分别存储在某一时刻t对应票数最多的人
    vector<int> clock;
    vector<int> p;

public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        int max=0,maxi=0,n=persons.size();
        unordered_map<int,int> count;  //记录每个人的票数
        for(int i=0;i<n;i++)
        {
            int num=++count[persons[i]];
            if(num>=max)
            {
                max=num;
                maxi=persons[i];
            }
            p.push_back(maxi);
            clock.push_back(times[i]);
        }
    }
    
    int q(int t) {
        //使用二分进行查找
        int pos=upper_bound(clock.begin(),clock.end(),t)-clock.begin();
        return p[pos-1];
    }
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */